package com.example.linked.fastslowpointers;

import com.example.linked.ListNode;

/**
 * 1.给定一个链表(不带头结点的链表)，判断链表中是否有环。
 *
 * <p>
 * 2.给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null
 * 输入：head = [3,2,0,-4], pos = 1
 * 输出：返回索引为 1 的链表节点
 * 解释：链表中有一个环，其尾部连接到第二个节点。
 */
public class Leetcode141_142_CycleList {
    public static void main(String[] args) {
//        ListNode head = new ListNode(-1);
        ListNode node1 = new ListNode(3);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(0);
        ListNode node4 = new ListNode(-4);
//        head.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node2;
        System.out.println(hasCycle(node1));
        System.out.println(hasCycle2(node2));
        System.out.println(detectCycle(node1).val);
    }

    /**
     * 1.1判断链表是否有环
     * 解法一:二次到达(暴力解法)
     * 思路:
     * 1.遍历链表时将链表存入某种数据结构中(数组，链表均可)
     * 2.每次将节点加入到数组(链表时)查看前面是否有该元素，
     * 如果有，则存在环
     * 如果遍历完整个链表，则不存在环
     *
     * @param head
     * @return
     */
    public static boolean hasCycle(ListNode head) {
        ListNode[] nodes = new ListNode[10000];
        ListNode cur = head;
        int i = 0;
        while (cur != null) {
            // 1.遍历链表，并将链表节点插入到数组中
            nodes[i] = cur;
            cur = cur.next;
            // 2.遍历之前的节点，判断当前这个节点是否在之前就已经插入了数组中
            // 如果已经插入，则有环
            for (int j = 0; j < i - 1; j++) {
                if (nodes[j] == nodes[i]) {
                    return true;
                }
            }
            i++;
        }
        return false;
    }

    /**
     * 1.1判断链表是否有环
     * 解法二：快慢指针解法
     * 1.定义快慢两个指针：
     * slow=head; fast=head.next;
     * 2.遍历链表：
     * 快指针步长为2：fast=fast.next.next;
     * 慢指针步长为1：slow=slow.next;
     * 3.当且仅当快慢指针重合，有环，返回true
     * 4.快指针为null，或其next指向null，没有环，返回false，操作结束
     *
     * @param head
     * @return
     */
    public static boolean hasCycle2(ListNode head) {
        // 只有一个结点的链表不可能成环
        if (head == null || head.next == null) {
            return false;
        }

        // 两个指针的初始位置可以相同也可以不同
        // fast可以在slow前面也可以在同一个位置，但是不能位于slow之后
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }

    /**
     * 2.给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null
     * <p>
     * 解法一:二次到达(暴力解法)
     * 思路:
     * 1.遍历链表时将链表存入某种数据结构中(数组，链表均可)
     * 2.每次将节点加入到数组(链表时)查看前面是否有该元素，
     * 如果有，则存在环，返回该节点即可
     * 如果遍历完整个链表，则不存在环
     *
     * @param head
     * @return
     */
    public static ListNode detectCycle(ListNode head) {
        ListNode[] nodes = new ListNode[10000];
        ListNode cur = head;
        int i = 0;
        while (cur != null) {
            // 1.遍历链表，并将链表节点插入到数组中
            nodes[i] = cur;
            cur = cur.next;
            // 2.遍历之前的节点，判断当前这个节点是否在之前就已经插入了数组中
            // 如果已经插入，则有环
            for (int j = 0; j < i - 1; j++) {
                if (nodes[j] == nodes[i]) {
                    return nodes[j];
                }
            }
            i++;
        }
        return null;
    }

    /**
     * 解法二:快慢指针法
     * 使用快慢指针找到是否有环（快指针一次走两步，慢指针一次走一步）
     * 找到环以后慢指针再回到头结点，之后快慢指针都按照步长1前进，等两个指针再次相遇就是环的入口位置。
     * 在学校田径运动中，跑的快的同学会套圈跑的慢的同学，这个其实就是和快慢指针的思路很像的。
     * <p>
     * 如果链表从的头结点就是环的入口，那就是一个标准环形跑道，慢的人跑完一整圈，
     * 正好被那个两倍速度的套圈，也就是两个人在起点相遇，
     *
     * 那么如果两个人不是在起点相遇，那么相差的距离其实就是头结点到环入口的距离。
     *
     * @param head
     * @return
     */
    public ListNode detectCycle2(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow)
                break; // 代表有环
        }
        if (fast == null || fast.next == null)
            return null;
        //慢指针回到链表头部
        slow = head;
        while (fast != slow) {
            slow = slow.next;
            fast = fast.next;//快指针也调整为一次走一步
        }
        return slow;
    }
}
